package stack_and_queue;

import java.util.PriorityQueue;
import java.util.Queue;

public class 数据流中的中位数 {
    class MedianFinder {
        Queue<Integer> A, B;
        public MedianFinder() {
            A = new PriorityQueue<>(); // 小顶堆，保存较大的一半
            B = new PriorityQueue<>((x, y) -> (y - x)); // 大顶堆，保存较小的一半
        }
        /*
        创建 PriorityQueue 实例：
            new PriorityQueue<>((x, y) -> (y - x))：创建一个新的 PriorityQueue 实例，并传入一个比较器。
        自定义比较器：
            (x, y) -> (y - x)：这是一个 lambda 表达式，定义了一个比较器。
            x 和 y 是两个待比较的元素。
            y - x 计算两个元素的差值。
        比较器的作用：
            当 y - x > 0 时，返回正值，表示 y 应该排在 x 之前。
            当 y - x < 0 时，返回负值，表示 x 应该排在 y 之前。
            当 y - x == 0 时，返回零，表示两个元素相等。
         */
        public void addNum(int num) {
            if(A.size() != B.size()) {
                A.add(num);
                B.add(A.poll());
            } else {
                B.add(num);
                A.add(B.poll());
            }
        }
        public double findMedian() {
            return A.size() != B.size() ? A.peek() : (A.peek() + B.peek()) / 2.0;
        }
    }
}
